PHASE5: Build contraction based HighOrder2 graph

Summary
Based on contraction node/edge graph from PHASE4, this phase creates new contracted_edges of to-be graph. Then identifies, nearby contracted_edges and link them into contracted_edge_links. Finally -- using contracted_edge and contracted_edge_links, creates a new HighOrder2 graph

STEP1: Clean up any old scratch works
TRUNCATE TABLE contracted_edge;

STEP2: Adding shortcuts with more than 5 Contraction Depths
SELECT * FROM activity_log WHERE title='GenerateGraph: Completed' ORDER BY at DESC limit 10;
<<"maxEdgeId":"12337862395">>
NOTE:
maxEdgeId is largest ID used by generate-graph stage and hence first_edge_id after that will be for contracted edges

SET statement_timeout=3600000;
\set first_edge_id 12337862395

SELECT contraction_depth,COUNT(edge_id) FROM edge WHERE edge_id > :first_edge_id AND contraction_depth <> 0 GROUP BY contraction_depth ORDER BY contraction_depth DESC;
<<Runs for ~15min>>

Contraction Depth Histogram:
contraction_depth | count
-------------------+------------
20 | 3
19 | 1
18 | 4
17 | 17
16 | 48
15 | 119
14 | 397
13 | 889
12 | 1792
11 | 4240
10 | 10796
9 | 37276
8 | 186388
7 | 709624
6 | 2415205
5 | 8723003
4 | 39835646
3 | 207462594
2 | 978456218
1 | 3299378722

NOTE:
Total edges with >= 4 edges" is: 51925448; >=5 is: 12089802

SELECT * FROM activity_log WHERE title='GenerateGraph: Completed' ORDER BY at DESC limit 10;
<<"maxEdgeId":"12337862395"; "maxEdgeId":"933119931">>
NOTE:
maxEdgeId is largest ID used by generate-graph stage and hence first_edge_id after that will be for contracted edges

SET statement_timeout=9600000;

SELECT 4 AS min_contraction_depth, 10000000 AS batch_size, 12337862395 AS first_edge_id \gset

TRUNCATE TABLE contracted_edge;
CALL g2k_extract_contracted_edges(:min_contraction_depth, :batch_size, :first_edge_id);
NOTE:
Runs for 1hr

SELECT COUNT(*) FROM contracted_edge;
<<Returns: 51925448>>

SELECT contraction_depth,COUNT(edge_id) FROM contracted_edge GROUP BY contraction_depth ORDER BY contraction_depth DESC;
contraction_depth | count
-------------------+----------
20 | 3
19 | 1
18 | 4
17 | 17
16 | 48
15 | 119
14 | 397
13 | 889
12 | 1792
11 | 4240
10 | 10796
9 | 37276
8 | 186388
7 | 709624
6 | 2415205
5 | 8723003
4 | 39835646

STEP3: Populating shortcut geometries
This step will expand contracted edges by underlying uncontracted edges.
Also, it extracts edgeIds/nodeIds and point/line lat/lon to the table: contracted_edge

STEP5a: Populating geom and distance of shortcuts
SELECT COUNT(*) FROM contracted_edge;
<<Returns: 44735738>>

SET statement_timeout=9600000; SET lock_timeout=1200000; SET work_mem TO '512MB';
SET statement_timeout=1800000; SET work_mem TO '256MB';
CALL g2k_update_contracted_edge_distance(0, 20);
CALL g2k_update_contracted_edge_distance(20, 40);
CALL g2k_update_contracted_edge_distance(40, 60);
CALL g2k_update_contracted_edge_distance(60, 80);
CALL g2k_update_contracted_edge_distance(80, 100);

SELECT MIN(distance), MAX(distance), AVG(distance) FROM contracted_edge;
min | max | avg
-----+---------------------+-----------------------
0 | 0.00714664501706132 | 0.0019149804815543686
NOTE: longest edge is 0.71km with average of 0.191km

Result of contracted_edges are the long paths all across the graph:

Ref: C:\GangaToKaveri\docs\g2k_contracted_shortcut_links_zoomed.png

STEP7: Populating nearest_contracted_edges by touching and non-touching edges
NOTE: nearest_contracted_edges is used by "Linking neighborhood shortcuts" tasks

Connect to database container
SET statement_timeout=1800000;

CREATE UNLOGGED TABLE IF NOT EXISTS nearest_contracted_edges_tmp (
src_contracted_edge_id bigint NOT NULL,
dst_contracted_edge_id bigint NOT NULL,
distance double precision NOT NULL
);
ALTER TABLE nearest_contracted_edges_tmp ADD CONSTRAINT nearcntrctdedgetukey UNIQUE(src_contracted_edge_id,dst_contracted_edge_id);

nohup ${PCH_APP_HOME}/run_G2KContractedEdgeLinker.sh --action runBuildNearestContractedEdges > $PCH_LOG_HOME/nohup.out 2>&1 &

NOTE:
Runs in executorThreads count of concurrent threads of batches of buildNearestContractedEdgeBatchRows
executorBusyTillThreadsRunning allows the task to re-feed the concurrent executor with next batch of tasks if busy threads falls below this number
Runs for ~300min -- creating 178899996 entries
runBuildNearestContractedEdges activities are 100% done in database using light Java processes. Hence you can colocate java container in database server.

  "graphDBConnectionInitSql": "SET statement_timeout = 4800000; SET lock_timeout=2400000;",

  "graphDBConnectionInitSql": "SET statement_timeout = 4800000; SET lock_timeout=2400000;",

SELECT COUNT(*) FROM nearest_contracted_edges_tmp;

    On PROD:
      count
    ---------
    178899996

    Returns:
      count
    ---------
    178899996

Verify (count should be zero) that all src edges have atleast one dst edge not touching each other:
SELECT COUNT(DISTINCT src_contracted_edge_id) FROM nearest_contracted_edges_tmp
WHERE 1=1
AND distance = 0
AND src_contracted_edge_id NOT IN (
SELECT DISTINCT src_contracted_edge_id FROM nearest_contracted_edges_tmp
WHERE distance > 0);
<<count should be zero>>

TRUNCATE TABLE nearest_contracted_edges;

\set NEAREST_SHORTCUTS_TO_LINK 4

INSERT INTO nearest_contracted_edges (src_contracted_edge_id, dst_contracted_edge_id, distance)
SELECT src_contracted_edge_id,dst_contracted_edge_id,distance FROM (
SELECT ROW_NUMBER() OVER (PARTITION BY src_contracted_edge_id ORDER BY distance) AS row_by_dist, nearest.*
FROM nearest_contracted_edges_tmp AS nearest) AS row_counted_nearest
WHERE row_counted_nearest.row_by_dist <= :NEAREST_SHORTCUTS_TO_LINK;
<<INSERT 0 178899996>>

DROP TABLE nearest_contracted_edges_tmp;
SELECT MIN(distance), MAX(distance), AVG(distance) FROM nearest_contracted_edges;
min | max | avg
------------------------+---------------------+-----------------------
0.00027777777776805124 | 0.07111165364376422 | 0.0016966237697779352
NOTE: farthest contracted-edge to be linked is 0.71km; average is 0.17km

Remove abnormal nearest links:
SELECT * FROM nearest_contracted_edges WHERE distance > 0.06;
id | src_contracted_edge_id | dst_contracted_edge_id | distance
-----------+------------------------+------------------------+-------------------
78247019 | 14475201694 | 14599649265 | 0.060123789
78247020 | 14475201694 | 16669695116 | 0.064834553
78247021 | 14475201694 | 16669695117 | 0.065432553
78247022 | 14475201694 | 14600566211 | 0.066432553
210051595 | 16345482682 | 14599649265 | 0.06783455
210051596 | 16345482682 | 16669695116 | 0.07000165
210051597 | 16345482682 | 16669695117 | 0.07110065
210051598 | 16345482682 | 14600566211 | 0.07111165

DELETE FROM nearest_contracted_edges WHERE id IN (78247019,78247020,78247021,78247022,210051595,210051596,210051597,210051598);

SELECT MIN(distance), MAX(distance), AVG(distance) FROM nearest_contracted_edges;
min | max | avg
------------------------+---------------------+-----------------------
0.00027777777776805124 | 0.01503339903080579 | 0.0016624573080090011

NOTE: farthest contracted-edge to be linked is 1.5km; but average distance is 0.16km

STEP9a: Linking neighborhood shortcuts (populating the table: contracted_edge_links)

NOTE:
nearestShortcutsToLink is selected 4 for DEV and 5 for PROD -- as higher value creates unmanageable super-mega clusters
nearestShortcutsToLink should be what was used as NEAREST_SHORTCUTS_TO_LINK in script while populating nearest_contracted_edges
secondaryCacheNodeSize can be large for "FORWARD" only search and hence is 6291456 for DEV on 32GB 9437184 on 64GB; 14680064 for PROD on 128GB
Shortcut caches are disabled since shortcuts should be calculated fresh.
For build action, fetchBatchSize should be multiple of nearestShortcutsToLink
batchedNodeAccessBatchSlots is set to -1 to disable batched MapData access -- as it is slow for light-weight forward-only
executorThreads is set to 7 for DEV on 8 core system; 40 on 48 core PROD system
On PROD, graphDBPoolSize is set to 35 (from 30) in prod to support 32 threads (PostGreSQL's max_connections=40)
maxNeighborCost thru solutionToEdgeRatioProfitableLimits are increased from contraction's values to make Dijkstra to search deeper and wider
skipNearestShortcutsToLinkNodesPct decides how many shortest paths to nearest edges are included. They are skipped if number of nodes in paths is < 50% to each other

nohup ${PCH_APP_HOME}/run_G2KContractedEdgeLinker.sh --action buildContractedEdgeLinks > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
The script will run for (TOTAL_CONTRACTED_EDGES*NEAREST_SHORTCUTS_TO_LINK/TOTAL_CONTRACTED_EDGES_PER_BATCH)+1 times
Each batch of 900000 rows run for ~70min/batch and completes all batches in ~5 days

STEP9b: Populating shortcut-link distances
SET statement_timeout=9600000;

CALL g2k_update_contracted_edge_links_distance(0, 20);
CALL g2k_update_contracted_edge_links_distance(20, 40);
CALL g2k_update_contracted_edge_links_distance(40, 60);
CALL g2k_update_contracted_edge_links_distance(60, 80);
CALL g2k_update_contracted_edge_links_distance(80, 101);

NOTE:
It runs for 10min
You can parallelize using multiple sessions

SELECT COUNT(*) FROM contracted_edge_links;
On PROD:
count
---------
72984124

SELECT MIN(distance), MAX(distance), AVG(distance) FROM contracted_edge_links;

          min           |         max         |         avg
------------------------+---------------------+----------------------
 0.00027777777776805124 | 0.09849835194712261 | 0.001632588301654219

          min           |         max         |         avg
------------------------+---------------------+----------------------
 0.00027777777776805124 | 0.09849835194712261 | 0.001632588301654219

NOTE: longest edge on PROD is 9.8km and average of 0.16km